﻿using log4net;
using System.Collections.Generic;
using System.Linq;
using VisioERLeveller.Model;

namespace VisioERLeveller {

    public class LevellizeResult {

        public LevellizeResult(Dictionary<Node, int> nodeLevels, int maxDepth, int rings = 0, int maxRingLength = 0) {
            this.NodeLevels = nodeLevels.ToDictionary(kvp => kvp.Key.ID, kvp => kvp.Value);
            this.MaxDepth = maxDepth;
            this.Rings = rings;
            this.MaxRingLength = maxRingLength;
        }

        public Dictionary<string, int> NodeLevels { get; }
        public int MaxDepth { get; }
        public int Rings { get; }
        public int MaxRingLength { get; }
    }

    public class Leveller {

        private static readonly ILog LOG = LogManager.GetLogger(typeof(Leveller));

        public LevellizeResult Levellize(Graph graph) {
            // TODO: 需要增加对 rings 的详细输出: 具体是哪几个ring, 然后对应的出口分别在哪里
            graph = graph.Copy();
            LOG.Info("Levellizing");
            Dictionary<Node, int> resultMap = new();
            int depth = this.RootFirstReduce(resultMap, graph, -1);
            int maxRingLength = 0;
            int rings = 0;

            while (graph.NodeCount > 0) {
                LOG.Info("Rings detected, searching ring details");
                Graph copy = graph.Copy();
                Dictionary<string, int> ringInfo = this.FindRingBreaks(copy);
                this.BreakRings(graph, ringInfo.Keys);
                LOG.Info("Rings broken");

                rings += ringInfo.Count;
                int max = ringInfo.Values.Max();
                maxRingLength = max > maxRingLength ? max : maxRingLength;

                depth = this.RootFirstReduce(resultMap, graph, depth);
            }

            return new LevellizeResult(resultMap, depth, rings, maxRingLength);
        }

        private int RootFirstReduce(Dictionary<Node, int> resultMap, Graph graph, int startLevel) {
            if (graph.NodeCount == 0)
                return startLevel;

            int depth = startLevel;
            List<Node> toRemove = new();
            do {
                foreach (Node node in toRemove) {
                    resultMap.Add(node, depth);
                    graph.Reduce(node);
                    LOG.Debug($"{depth}: Node {node.Name} reduced");
                }
                depth++;

                toRemove.Clear();
                this.RootFirstSearch(toRemove, graph);
                LOG.Debug($"Depth={depth}, {toRemove.Count} nodes found");
            } while (toRemove.Count > 0);
            return depth - 1;
        }

        private void RootFirstSearch(List<Node> resultSet, Graph graph) {
            foreach (Node node in graph.Nodes) {
                if (!node.IsRooted) continue;
                resultSet.Add(node);
            }
        }

        private void LeafFirstReduce(Graph graph) {
            if (graph.NodeCount == 0)
                return;

            List<Node> toRemove = new();
            do {
                foreach (Node node in toRemove)
                    graph.Reduce(node);

                toRemove.Clear();
                this.LeafFirstSearch(toRemove, graph);
            } while (toRemove.Count > 0);
        }

        private void LeafFirstSearch(List<Node> resultSet, Graph graph) {
            foreach (Node node in graph.Nodes) {
                if (!node.IsLeaf) continue;
                resultSet.Add(node);
            }
        }

        private Dictionary<string, int> FindRingBreaks(Graph graph) {;
            this.ReduceSelfLoop(graph);
            List<IEnumerable<string>> rings = new();
            Dictionary<string, int> ringBreaks = new();
            while (true) {
                this.RootFirstReduce(new(), graph, 0);
                this.LeafFirstReduce(graph);
                
                var ring = this.FindRing(graph);
                var len = ring.Count();
                if (len == 0)
                    break;

                rings.Add(ring);
                
                var breakpoint = this.FindBreak(graph, ring);
                if (breakpoint is null)
                    continue;

                ringBreaks.Add(breakpoint.ID, len);
                graph.Remove(breakpoint);
            }
            return ringBreaks;
        }

        private Link FindBreak(Graph graph, IEnumerable<string> links) {
            foreach (var linkId in links) {
                var link = graph.GetLink(linkId);
                if (link.Type == LinkType.NotNull) continue;
                return link;
            }
            return null;
        }

        private void ReduceSelfLoop(Graph graph) {
            List<Link> toRemove = new();
            foreach (var link in graph.Links) {
                if (link.FromId != link.ToId)
                    continue;
                toRemove.Add(link);
            }
            foreach (var link in toRemove) {
                graph.Remove(link);
            }
        }

        private IEnumerable<string> FindRing(Graph graph) {
            if (graph.NodeCount == 0)
                return new List<string>();

            foreach (Node node in graph.Nodes)
                node.Tag<List<string>>(null);

            Queue<string> tasks = new();

            Node feed = graph.Nodes.First();
            feed.Tag(new List<string>());
            tasks.Enqueue(feed.ID);

            IEnumerable<string> minRing = null;

            while (tasks.Count > 0) {
                string fromId = tasks.Dequeue();
                Node from = graph.GetNode(fromId);
                var fromTag = from.Tag<List<string>>();
                var firstLinkId = fromTag.FirstOrDefault();
                var firstLink = firstLinkId is not null ? graph.GetLink(firstLinkId) : null;
                foreach (string linkId in from.Links) {
                    Link link = graph.GetLink(linkId);
                    if (link.FromId != fromId) continue;
                    string toId = link.ToId;
                    
                    if (fromTag.Count > 0 && toId == firstLink.FromId) {
                        if (minRing is null || fromTag.Count + 1 < minRing.Count())
                            minRing = new List<string>(fromTag) { linkId };
                        continue;
                    }

                    Node to = graph.GetNode(toId);
                    var toTag = to.Tag<List<string>>();
                    if (toTag is not null && toTag.Count < fromTag.Count + 1)
                        continue;

                    toTag = new(fromTag) { linkId };
                    to.Tag(toTag);

                    tasks.Enqueue(toId);
                }
            }

            return minRing;
        }

        private void BreakRings(Graph graph, IEnumerable<string> links) {
            foreach (var linkId in links) {
                var link = graph.GetLink(linkId);
                graph.Remove(link);
            }
        }

    }

}
